#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;


 // Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
   TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
 

class Solution {
    unordered_map<int, int> mp;
public:
    TreeNode* mybuild(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int ol, int orr) {
        if (pl > pr || ol > orr)return nullptr;
        int root_pp = pl;
        int root_po = mp[preorder[root_pp]];
        TreeNode* root = new TreeNode(preorder[root_pp]);
        int lsz = root_po - ol;
        int rsz = orr -root_po + 2;

        root->left = mybuild(preorder, inorder, pl + 1, pl + lsz, ol, root_po - 1);
        root->right = mybuild(preorder, inorder, pl + lsz + 1, pr, root_po + 1, orr);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for (int i = 0; i < inorder.size(); i++) {
            mp[inorder[i]] = i;
        }
        return mybuild(preorder, inorder, 0, n - 1, 0, n - 1);
    }


};


int main() {
    vector<int> pre = { 3,9,20,15,7 };
    vector<int> ord = { 9,3,15,20,7 };
    Solution t;
    t.buildTree(pre, ord);


    return 0;
}